#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=105;

int n,k,m,s,t;
vector<int> edges[N];
int type[N];
vector<int> resist[N];
LL ans=INT_MAX;
LL w0[N];
LL edges0[N][N];

int visit[N];
void dfs(int p,LL curw)
{
	if(curw+edges0[p][t]>=ans) return;
    if(p==t)
    {
        ans=min(ans,curw);
        return;
    }
    int size=edges[p].size();
    for(int i=0;i<size;i+=2)
    {
        int t=edges[p][i];
        LL w=(LL)edges[p][i+1];
        if(visit[type[t]]==0)
        {
            for(auto u:resist[type[t]])
            {
                visit[u]++;
            }
            dfs(t,curw+w);
            for(auto u:resist[type[t]])
            {
                visit[u]--;
            }
        }
    }
}

int main()
{
    scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&type[i]);
    }
    
    for(int i=1;i<=k;i++)
    {
        resist[i].emplace_back(i);
        for(int j=1;j<=k;j++)
        {
        	int u;
            scanf("%d",&u);
            if(u==1)
            {
                resist[j].emplace_back(i);
                //resist[i][j]=true;
            }
            //else resist[i][j]=false;        
        }
    }
    
	memset(edges0,0x3f,sizeof(edges0));
	for(int i=1;i<=n;i++)
	{
		edges0[i][i]=0;
	}
    for(int i=1;i<=m;i++)
    {
        int s,t,w;
        scanf("%d%d%d",&s,&t,&w);
        edges[s].emplace_back(t);
        edges[s].emplace_back(w);
        edges[t].emplace_back(s);
        edges[t].emplace_back(w);
        edges0[s][t]=edges0[t][s]=w;
    }
    for(int k=1;k<=n;k++)
    {
    	for(int s=1;s<=n;s++)
    	{
    		for(int t=1;t<=n;t++)
    		{
    			if(edges0[s][t]>edges0[s][k]+edges0[k][t])
    			{
    				edges0[s][t]=edges0[s][k]+edges0[k][t];
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<edges0[i][j]<<' ';
		}
		cout<<endl;
	}
    memset(visit,0,sizeof(visit));
    for(auto u:resist[ type[s] ])
    {
        visit[u]++;
    }
    dfs(s,0);

    if(ans==INT_MAX) printf("-1");
    else printf("%d",ans);
    return 0;
}
